package chujisuanfa;

public class Moving {

    int[][] gard;
    int res=0;
    public int movingCount(int m, int n, int k) {
        gard = new int[m][n];
        dfs(0,0,k,m,n);
        return res;
    }
    public void dfs(int i,int j,int k,int m,int n){
        int sum = 0,ic=i,jc=j;
        while(ic>=10){
            sum+=ic%10;
            ic/=10;
        }
        sum+=ic;
        while(jc>=10){
            sum+=jc%10;
            jc/=10;
        }
        sum+=jc;
        if(i<0||j<0||i>=m||j>=n||sum>k||gard[i][j]==1) return;
        gard[i][j]=1;
        res++;
        dfs(i+1,j,k,m,n);
        dfs(i,j+1,k,m,n);
        dfs(i-1,j,k,m,n);
        dfs(i,j-1,k,m,n);

    }
    public static void main(String[] args) {
        Moving f = new Moving();
        System.out.println(f.movingCount(11,8,16));
        for(int i=0;i<11;++i){
            for (int j= 0;j<8;++j){
                System.out.print(i+j);
                System.out.print("  ");
            }
            System.out.println();
        }
    }
}
